package com.fps.webshop.question.question0200_0299;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 217. 存在重复元素
 * 
 * 给定一个整数数组，判断是否存在重复元素。
 * 
 * 如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。
 * 
 * 示例 1:
 * 输入: [1,2,3,1]
 * 输出: true
 * 
 * 示例 2:
 * 输入: [1,2,3,4]
 * 输出: false
 * 
 * 示例 3:
 * 输入: [1,1,1,3,3,4,3,2,4,2]
 * 输出: true
 * 
 */
public class Question217 {
	
	
	/**
	 * 第一次提交，使用了最容易想到的方式，就是通过map去进行判断，但这么做的缺点也很明显
	 * 时间并不理想
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注
	 * 通过		8 ms	44.9 MB	Java	2021/08/10 10:09
	 */
	public static boolean containsDuplicate1(int[] nums) {
		Map<Integer,Integer> map = new HashMap<Integer,Integer>();
		for(int num:nums) {
			if(map.get(num)!=null) {
				return true;
			}else {
				map.put(num, num);
			}
		}
		return false;
    }
	
	/**
	 * 第二次提交，试图使用双层循环对数组元素进行比较，但是超时了
	 * 提交结果		执行用时	内存消耗	语言		提交时间				备注
	 * 超出时间限制	N/A		N/A		Java	2021/08/10 10:14
	 */
	public static boolean containsDuplicate2(int[] nums) {
		for(int i = 0;i<nums.length-1;i++) {
			for(int j=i+1;j<nums.length;j++) {
				if(nums[i]==nums[j]) {
					return true;
				}
			}
		}
		return false;
    }
	
	/**
	 * 第三次提交，不使用map，而是选择使用set，时间反而增加了，估计频繁读写set依旧耗时
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注
	 * 通过		9 ms	44.3 MB	Java	2021/08/10 10:33
	 */
	public static boolean containsDuplicate3(int[] nums) {
		Set<Integer> set = new HashSet<Integer>();
		for(int num:nums) {
			if(set.contains(num)) {
				return true;
			}else {
				set.add(num);
			}
		}
		return false;
    }
	
	/**
	 * 第四次提交，依旧使用set，但想到set.add本身就会判断当前set中是否已存在需要添加的元素，不需要在及逆行一次额外判断
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注
	 * 通过		5 ms	42.5 MB	Java	2021/08/10 10:36
	 */
	public static boolean containsDuplicate4(int[] nums) {
		Set<Integer> set = new HashSet<Integer>(); 
		for (int x : nums) { 
			if(!set.add(x)) { 
				return true; 
			} 
		} 
		return false;
    }
	
	/**
	 * 第五次提交，使用Arrays.sort进行排序，再进行一次循环的比较
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注
	 * 通过		3 ms	41.5 MB	Java	2021/08/10 10:24
	 */
	public static boolean containsDuplicate5(int[] nums) {
		Arrays.sort(nums);
        int n = nums.length;
        for (int i = 0; i < n - 1; i++) {
            if (nums[i] == nums[i + 1]) {
                return true;
            }
        }
        return false;
    }
	
	
	public static void main(String[] args) {
		int[] nums = new int[] {1,2,3,1};
		System.out.print(containsDuplicate1(nums));
	}
}
